#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include <time.h>
#include <Windows.h>


// 将 字符串 p[start_pos,end_pos) 中的数字字符转为对应的数字
// 比如 my_atoi("012345", 3, 5) 指的是将 "34" 转为 34
int my_atoi(char* p, int start_pos, int end_pos) {
    char t[20];
    int len = end_pos-start_pos;
    memcpy(t, p+start_pos, len);
    t[len] = 0;
    return atoi(t);
}


// 下面是身份证相关内容 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
// 这块代码不是很容易懂, 建议网上自行搜索 身份证每个字段的含义的规则

int ratioValueArray[] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char matchCheckValueArray[] = {'1','0','X','9','8','7','6','5','4','3','2'};

// 验证身份证的校验位是否正确, 身份证的校验位设计还是很牛逼的
int validateCheckNum(char* identityNumber) {
    int len = strlen(identityNumber);
    if (18 == len) {
        int sum = 0;
        for (int i=0; i<17; ++i) {
            sum += (identityNumber[i]-'0') * ratioValueArray[i];
        }
        return matchCheckValueArray[sum%11] == identityNumber[17];
    } else {
        return 1;
    }
}

/**
 * 验证 身份证字符串 的合法性
 * */
int validateIdentityNumber(char* identityNumber) {
    if (NULL == identityNumber) {
        return 0;
    }
    int len = strlen(identityNumber);
    if (18 != len && 15 != len) {
        return 0;
    }

    // 验证字符
    int validateLen = (18==len && 'X'==identityNumber[17]) ? 17 : len;
    for (int i=0; i<validateLen; ++i) {
        char ch = identityNumber[i];
        if (ch < '0' || '9' < ch) {
            return 0;
        }
    }

	// 验证区域码 (如果需要更完整的校验, 需要每年从国家权威机构更新 新政区划数据)
    unsigned long long regionCode = my_atoi(identityNumber, 0, 6);
    if (regionCode < 110000 || 659999 < regionCode) {
        return 0;
    }

	// 验证 月份和日期
    int month, day;
    if (18 == len) {
        int year = my_atoi(identityNumber, 6, 10);
        if (year < 1830) {
            return 0;
        }
        month = my_atoi(identityNumber, 10, 12);
        day = my_atoi(identityNumber, 12, 14);
    } else {
        month = my_atoi(identityNumber, 8, 10);
        day = my_atoi(identityNumber, 10, 12);
    }
    if (month < 1 || 12 < month) {
        return 0;
    }
    if (day < 1 || 31 < day) {
        return 0;
    }

    return validateCheckNum(identityNumber);
}

/**
 * 将 身份证字符串 转化为 long类型数值
 * */
unsigned long long convertIdentityNumberStrToLong(char* identityNumber) {
    /**
     * 地址码的范围是: 110000~659999
     * 减去 100000 范围是 010000~559999
     * 可使用16个bit位表示
     * */
    unsigned long long regionCode = my_atoi(identityNumber, 0, 6) - 100000;

    int len = strlen(identityNumber);
    if (18 == len) {
        /**
         * 出生年范围为 1830~9999
         * 转化之后出生年月日数值范围为 : 0~3137278
         * 可使用22个bit位表示
         * */
        int year = my_atoi(identityNumber, 6, 10) - 1830;
        int month = my_atoi(identityNumber, 10, 12) - 1;
        int day = my_atoi(identityNumber, 12, 14) - 1;
        unsigned long long date = (year*12 + month)*32 + day;

        /**
         * 顺序码 格式为 0000~9999 或者 000X~999X
         * 转化后 数值范围为 0~19999
         * 可使用15个bit位表示
         * */
        unsigned long long serialCode;
        if ('X' == identityNumber[17]) {
            serialCode = my_atoi(identityNumber, 14, 17);
        } else {
            serialCode = my_atoi(identityNumber, 14, 18) + 10000;
        }

        return (regionCode << 37) | (date << 15) | (serialCode);
    } else if (15 == len) {
        /**
         * 出生年范围为 00~99
         * 转化之后出生年月日数值范围为 : 0~38016
         * 可使用16个bit位表示
         * */
        int year = my_atoi(identityNumber, 6, 8);
        int month = my_atoi(identityNumber, 8, 10) - 1;
        int day = my_atoi(identityNumber, 10, 12) - 1;
        unsigned long long date = (year*12 + month)*32 + day;

        /**
         * 顺序码 格式为 000~999
         * 可使用10个bit位表示
         * */
        unsigned long long serialCode = my_atoi(identityNumber, 12, 15);

        return (regionCode << 26) | (date << 10) | (serialCode);
    }

    return 0;
}

/*
该测试样例 用不上的方法:

char dateIntToStrTmpResult[32];
char* dateIntToStr(int date, int startYear, int yearStrLength) {
    int day = (date&31) + 1;
    int monthAndYear = (date - (day-1)) >> 5;
    int month = monthAndYear % 12 + 1;
    int year = monthAndYear / 12 + startYear;
    char* formatStr = (4 == yearStrLength) ? "%04d%02d%02d" : "%02d%02d%02d";
    sprintf(dateIntToStrTmpResult, formatStr, year, month, day);
    return dateIntToStrTmpResult;
}

// 一代身份证转化为数值最小值
unsigned long long minValueOfFirstID = convertIdentityNumberStrToLong("110000000101000");
// 一代身份证转化为数值最大值
unsigned long long maxValueOfFirstID = convertIdentityNumberStrToLong("659999991231999");
// 二代身份证转化为数值最小值
unsigned long long minValueOfSecondID = convertIdentityNumberStrToLong("11000018300101000X");
// 二代身份证转化为数值最大值
unsigned long long maxValueOfSecondID = convertIdentityNumberStrToLong("659999999912319999");
// 将 long类型数值 转化为 身份证字符串
char convertLongToIdentityNumberStrTmpResult[20];
char* convertLongToIdentityNumberStr(unsigned long long value) {
    if (minValueOfSecondID <= value && value <= maxValueOfSecondID) {
        unsigned long long regionCode = value >> 37;

        int date = (int) (value >> 15) & ((1<<22)-1);
        char* dateStr = dateIntToStr(date, 1830, 4);

        unsigned long long serialCode = value & ((1<<15)-1);
        char serialCodeStr[16];
        if (serialCode >= 10000) {
            sprintf(serialCodeStr, "%04d", serialCode-10000);
        } else {
            sprintf(serialCodeStr, "%03dX", serialCode);
        }

        sprintf(convertLongToIdentityNumberStrTmpResult, "%d%s%s", regionCode+100000, dateStr, serialCodeStr);
        return convertLongToIdentityNumberStrTmpResult;
    } else if (minValueOfFirstID <= value && value <= maxValueOfFirstID) {
        unsigned long long regionCode = value >> 26;

        int date = (int) (value >> 10) & ((1<<16)-1);
        char* dateStr = dateIntToStr(date, 0, 2);

        unsigned long long serialCode = value & ((1<<10)-1);

        sprintf(convertLongToIdentityNumberStrTmpResult, "%d%s%03d", regionCode+100000, dateStr, serialCode);
        return convertLongToIdentityNumberStrTmpResult;
    } else {
        //throw new RuntimeException("invalid value" + value);
    }
}
*/
// 上面是身份证相关内容 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑



// 下面是hash相关内容 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
// 计算hash值
int hash_func(unsigned long long val, int max)
{
    char* p = (char*) (&val);	// 将 long long 当做 8 个字符处理

    int h = 0;
    for (int i = 0; i < 8; ++i) {
		// 网上随便找的hash方法
        h = (h << 4) ^ (h >> 28) ^ p[i];
    }

    h = h % max;
    if (h < 0) h += max;

    return h;
}
// 插入到hash表
void insert_to_hashmap(unsigned long long * hashmap, int hashmap_size, unsigned long long val)
 {
    int hash_val = hash_func(val, hashmap_size);

    int idx;
    // 遍历hashmap, 坐标范围 [hash_val, hashmap_size)
    for (idx=hash_val; idx<hashmap_size; ++idx)
    {
        if (hashmap[idx] == 0) 
        {
            hashmap[idx] = val;
            return;
        }
    }
    // 遍历hashmap, 坐标范围 [0, hash_val)
    for (idx=0; idx<hash_val; ++idx)
    {
        if (hashmap[idx] == 0) 
        {
            hashmap[idx] = val;
            return;
        }
    }
 }
 // 在hash表中搜索
 int search_in_hashmap(unsigned long long * hashmap, int hashmap_size, unsigned long long val)
 {
    int hash_val = hash_func(val, hashmap_size);

    int idx;
    // 遍历hashmap, 坐标范围 [hash_val, hashmap_size)
    for (idx=hash_val; idx<hashmap_size; ++idx)
    {
        if (hashmap[idx] == 0) 
        {
            return -1;
        } 
        else if (hashmap[idx] == val) 
        {
            return idx;
        }
    }
    // 遍历hashmap, 坐标范围 [0, hash_val)
    for (idx=0; idx<hash_val; ++idx)
    {
        if (hashmap[idx] == 0) 
        {
            return -1;
        } 
        else if (hashmap[idx] == val) 
        {
            return idx;
        }
    }
 }
// 上面是hash相关内容 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑



// long long 类型的比较函数
int long_long_cmp(const void * a, const void * b) {
    return *((unsigned long long *) a) - *((unsigned long long *) b);
}


#define max_input_count 1000000

// 该测试方法使用 排序后的数组 做二分查找
void bySortedMemory()
{
	// 申请内存
    unsigned long long * id_arr = (unsigned long long *) malloc(max_input_count*sizeof(unsigned long long));

	// 初始化随机数生成器
    srand((unsigned int)time(NULL));

	// 
	unsigned long long random_id_val = convertIdentityNumberStrToLong("11000018300101000X");	// 防止个人身份证号码泄露, 可以填写实际的身份证号码
    int idx;
    for (idx=0; idx<max_input_count; idx++)
    {
        random_id_val += 127;//rand(); 也可以使用随机生成, 这样有可能查询不到, 做查询不到的测试 (有时间的可以写一个程序随机生成符合规则的身份证)
        id_arr[idx] = random_id_val;	// 将随机生成的加入到 id_arr
    }

    // 快排, id_arr存储的身份证号码有序, 才能使用二分查找
    qsort(id_arr, max_input_count, sizeof(unsigned long long), long_long_cmp);

	// 获取开始的毫秒数
    SYSTEMTIME start_time;
    GetSystemTime(&start_time);

    // 查询
    unsigned long long search_id = random_id_val;
    void * search_p;
    for (idx=0; idx<max_input_count; idx++)
    {
        // 二分查找
        search_p = bsearch(&search_id, id_arr, max_input_count, sizeof(unsigned long long), long_long_cmp);
        //if (search_p == NULL) printf("not found %ld\n", search_id);
        search_id -= 127;
    }

	// 打印运行时间
    SYSTEMTIME end_time;
    GetSystemTime(&end_time);
    printf("spend milliseconds = %d\n", (end_time.wMilliseconds - start_time.wMilliseconds));
    // 75 毫秒左右


	// 释放申请的内存
    free(id_arr);
}

#define hashmap_mem_size max_input_count*20
#define hashmap_size hashmap_mem_size/8
// 该测试方法使用hash表的方式进行搜索
void byHashMap()
{
	// 申请内存并将内存 全部设置为 0
    unsigned long long * hashmap = (unsigned long long *) malloc(hashmap_mem_size);
    memset(hashmap, 0, hashmap_mem_size);

    /*int idx=0;
    char id[20];
    for (idx=0; idx<max_input_count; idx++)
    {
        // todo 读取字符串
        strcpy(id, "110000000101000");
        unsigned long long id_val = convertIdentityNumberStrToLong(id);
        insert_to_hashmap(hashmap, hashmap_size, id_val);
    }*/

    // 初始化随机数生成器
    srand((unsigned int)time(NULL));

    unsigned long long random_id_val = convertIdentityNumberStrToLong("11000018300101000X");	// 防止个人身份证号码泄露, 可以填写实际的身份证号码
    int idx;
    for (idx=0; idx<max_input_count; idx++)
    {
        random_id_val += 1270;//rand(); 也可以使用随机生成, 这样有可能查询不到, 做查询不到的测试 (有时间的可以写一个程序随机生成符合规则的身份证)
        insert_to_hashmap(hashmap, hashmap_size, random_id_val);	// 将随机生成的插入到 hash表
    }

    // 查询
    /*char id[20];
    strcpy(id, "11000018300101000X");
    unsigned long long search_id = convertIdentityNumberStrToLong(id);*/
    unsigned long long search_id = random_id_val;
    int search_p;

	// 获取开始的毫秒数
    SYSTEMTIME start_time;
    GetSystemTime(&start_time);
    
    for (idx=0; idx<max_input_count; idx++)
    {
        search_p = search_in_hashmap(hashmap, hashmap_size, search_id);
        search_id -= 1270;
        //if (search_p < 0) printf("search_p = %d\n", search_p);
    }

	// 打印运行时间
    SYSTEMTIME end_time;
    GetSystemTime(&end_time);
    printf("spend milliseconds = %d\n", (end_time.wMilliseconds - start_time.wMilliseconds));
    // 88 毫秒左右

	// 释放申请的内存
    free(hashmap);
}


int main(void)
{
    bySortedMemory();
    byHashMap();

    //system("pause");
    return 0;
}